package zhupf.test.lruDemo;

import java.util.HashMap;
import java.util.Map;

/**
 *  lru实现，最近最少使用删除
 * @param <K>
 * @param <V>
 */
public class LruMap<K,V> {

    class Node<K,V>{
        K key;
        V value;
        Node<K,V> prev;
        Node<K,V> next;
        public Node(K key,V value){
            this.key = key;
            this.value = value;
            prev = next = null;
        }
        public Node(){}
    }

    class DoublicLinkedNode<K,V>{
        Node<K,V> heard ;
        Node<K,V> tail ;
        public DoublicLinkedNode(){
            heard = new Node<>();
            tail =  new Node<>();
            heard.next = tail;
            tail.prev = heard;
        }

        public void addHeard(Node<K,V> node){
            node.next = heard.next;
            heard.next.prev = node;
            heard.next = node;
            node.prev = heard;
        }

        public void remodeNode(Node<K,V> node){
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.prev = null;
            node.next = null;
        }
        public Node<K,V> getLastNode(){
            return tail.prev;
        }
    }

    private int captial;

    public Map<K,Node<K,V>> map;

    private DoublicLinkedNode<K,V> doublicLinkedNode;

    public LruMap(int captial){
        this.captial = captial;
        map = new HashMap<>(captial);
        this.doublicLinkedNode = new DoublicLinkedNode();
    }

    public V get(K key){
        if(!map.keySet().contains(key)){
            return null;
        }
        Node<K, V> node = map.get(key);
        doublicLinkedNode.remodeNode(node);
        doublicLinkedNode.addHeard(node);
        return node.value;
    }

    public void put(K key,V value){
        Node<K,V> node = new Node<>(key,value);
        if (map.keySet().contains(key)) {
            doublicLinkedNode.remodeNode(node);
        }else{
            if(map.keySet().size()>=captial){
                Node<K,V> lastNode = doublicLinkedNode.getLastNode();
                doublicLinkedNode.remodeNode(lastNode);
                map.remove(lastNode.key);
            }
        }
        map.put(key,node);
        doublicLinkedNode.addHeard(node);
    }
}
